Permutations and Combinations

Subject: Additional Mathematics
Topic: 8
Cambridge Code: 4037 / 0606

---

Fundamental Counting Principle

Fundamental Counting Principle - If one task can be done in $m$ ways and another in $n$ ways, both tasks can be done in $m \times n$ ways

Example

A restaurant menu has 3 appetizers, 5 main courses, 4 desserts. Number of possible 3-course meals: $3 \times 5 \times 4 = 60$

---

Factorial Notation

Factorial - Product of all positive integers from 1 to $n$

$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$

Special Cases

$0! = 1$ $1! = 1$ $2! = 2$ $3! = 6$ $4! = 24$ $5! = 120$

---

Permutations

Permutation - Arrangement where order matters

Permutations of n objects

Number of ways to arrange $n$ distinct objects: $P(n) = n!$

Example: Arrange 5 books on a shelf: $5! = 120 \text{ ways}$

Permutations of r objects from n

Number of arrangements of $r$ objects selected from $n$ objects:

$P(n, r) = {}^nP_r = \frac{n!}{(n-r)!}$

Or: ${}^nP_r = n(n-1)(n-2)\cdots(n-r+1)$

Example

Arrange 3 letters from A, B, C, D, E:

${}^5P_3 = \frac{5!}{2!} = \frac{120}{2} = 60$

Or: $5 \times 4 \times 3 = 60$

Permutations with Repetitions

Number of arrangements with $r$ choices from $n$ objects (repetition allowed):

$n^r$

Example: 4-digit PIN from digits 0-9: $10^4 = 10,000$

---

Combinations

Combination - Selection where order does NOT matter

Combinations of r objects from n

Number of ways to select $r$ objects from $n$ objects:

$C(n, r) = {}^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Example

Select 3 letters from A, B, C, D, E:

${}^5C_3 = \frac{5!}{3!2!} = \frac{120}{6 \times 2} = 10$

Relationship Between Permutations and Combinations

${}^nP_r = {}^nC_r \times r!$

This makes sense: to arrangey, first select (${}^nC_r$), then arrange the selection ($r!$)

---

Properties of Combinations

${}^nC_0 = 1$ ${}^nC_n = 1$ ${}^nC_r = {}^nC_{n-r}$

Example of Symmetry

${}^6C_2 = {}^6C_4 = 15$

---

Binomial Expansion

Binomial Theorem - Expansion of $(a+b)^n$:

$(a+b)^n = \sum_{r=0}^{n} {}^nC_r \cdot a^{n-r} \cdot b^r$

Or explicitly: $(a+b)^n = {}^nC_0 a^n + {}^nC_1 a^{n-1}b + {}^nC_2 a^{n-2}b^2 + \cdots + {}^nC_n b^n$

Example

Expand $(x+2)^3$:

$(x+2)^3 = {}^3C_0 x^3 + {}^3C_1 x^2(2) + {}^3C_2 x(2)^2 + {}^3C_3 (2)^3$

$= x^3 + 3x^2(2) + 3x(4) + 8$

$= x^3 + 6x^2 + 12x + 8$

---

Permutations with Identical Objects

When arranging $n$ objects where some are identical:

$\text{Number of arrangements} = \frac{n!}{n_1! \cdot n_2! \cdots n_k!}$

where $n_1, n_2, \ldots, n_k$ are frequencies of identical objects

Example

Arrange letters in MISSISSIPPI:

• Total letters: 11
• M: 1, I: 4, S: 4, P: 2

$\frac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = 34,650$

---

Circular Permutations

Circular Permutation - Arrangement in a circle (rotations considered identical)

For $n$ distinct objects: $(n-1)!$

Example

Arrange 4 people around a circular table: $(4-1)! = 3! = 6$

---

Key Points to Remember

1. Permutations: order matters - use ${}^nP_r$
2. Combinations: order doesn't matter - use ${}^nC_r$
3. Factorial: $n! = n(n-1)(n-2)\cdots 1$
4. Permutations formula: ${}^nP_r = \frac{n!}{(n-r)!}$
5. Combinations formula: ${}^nC_r = \frac{n!}{r!(n-r)!}$
6. Binomial theorem uses combinations as coefficients

---

Worked Examples

Example 1: Simple Permutation

How many 3-letter "words" can be formed from A, B, C, D (no repetition)?

${}^4P_3 = 4 \times 3 \times 2 = 24$

Example 2: Combination

A team of 5 is chosen from 12 people. How many ways?

${}^{12}C_5 = \frac{12!}{5!7!} = \frac{12 \times 11 \times 10 \times 9 \times 8}{5 \times 4 \times 3 \times 2 \times 1} = 792$

Example 3: Binomial Coefficient

Find the coefficient of $x^2$ in $(2x-3)^4$:

Using ${}^4C_2 (2x)^2(-3)^2$: ${}^4C_2 \times 4x^2 \times 9 = 6 \times 4 \times 9 \times x^2 = 216x^2$

Coefficient: 216

---

Practice Questions

1. Calculate:

   • ${}^6P_3$
   • ${}^8C_3$
   • ${}^7P_4 \div {}^7C_4$

2. How many ways can 6 people be arranged in a line?

3. From 10 students, choose 4 for a committee. How many ways?

4. Expand $(a-b)^4$

---

Revision Tips

• Permutation = arrangement (order matters)
• Combination = selection (order doesn't matter)
• Use factorial for all elements
• Use ${}^nP_r$ and ${}^nC_r$ formulas correctly
• Think about whether order matters in problem
• Binomial theorem: coefficients are combinations